package stu.day39_day.day43;

import java.util.Scanner;

public class hw4 {

    public static int fun1(int[] time,int[] price,int t){
        int n=time.length;
        int[][] dp = new int[n+1][t+1];

        for(int i=1;i<=n;i++){
            for(int j=0;j<=t;j++){
                if(time[i-1]>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-time[i-1]]+price[i-1]);
                }
            }
        }

        return dp[n][t];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] str = sc.nextLine().split(" ");
        int t = Integer.parseInt(str[0]);
        int n = Integer.parseInt(str[1]);

        int[] time = new int[n];
        int[] price = new int[n];
        for (int i = 0; i < n; i++) {
            String[] str1 = sc.nextLine().split(" ");
            time[i] = Integer.parseInt(str1[0]);
            price[i] = Integer.parseInt(str1[1]);
        }

        System.out.println(fun1(time,price,t));


    }
}
